/*************************************************************************
	> File Name: 005.HZOJ-49.多重背包.cpp
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 二  6/29 12:28:25 2021
 ************************************************************************/

#include <iostream>
using namespace std;

//多重背包二进制优化

//ind为拆完后的物品数量
int V, n, ind = 1, v[20005], w[20005], ans[100005];
int bit2[25]; //二进制数组

void init() {
    int t = 1;
    for (int i = 0; i < 21; i++) {
        bit2[i] = t;
        t *= 2;
    }
}

int main() {
    init();
    cin >> V >> n;
    for (int i = 1; i <= n; i++) {
        int a, b, c, cnt = 0;
        cin >> a >> b >> c;
        while (c) { //拆分
            if (c > bit2[cnt]) {
                v[ind] = a * bit2[cnt];
                w[ind] = b * bit2[cnt];
                c -= bit2[cnt];
                cnt++;
            } else {
                v[ind] = a * c;
                w[ind] = b * c;
                c = 0;
            } 
            ind++;
        }
    }
    //求解0/1背包
    for (int i = 1; i <= ind; i++) {
        for (int j = V; j >= v[i]; j--) {
            ans[j] = max(ans[j], ans[j - v[i]] + w[i]);
        }
    }
    cout << ans[V] << endl;

    return 0;
}
